public enum SelectionSort implements Sort{
    INSTANCE;

    /**
     * arr[i,n)未排序，arr[0,i) 已排序
     * sort的基本逻辑是，从前向后扫描，对于每一个i，寻找arr[i,n)区间的最小值，记住这个最小值的索引是minIndex，
     * 然后，只需要每次将arr[i] 和 arr[maxIndex]交换位置即可。
     * <p>
     * 在sort中，从前向后，每次找后面未排序部分的最小值，和arr[i]交换
     *
     * @param arr
     * @param <E>
     */
    @Override
    public <E extends Comparable<E>> void sort(E[] arr) {
        for (int i = 0; i < arr.length; i++) {  //n
            //选择arr[i..n)中最小值的索引
            int minIndex = i;
            for (int j = i; j < arr.length; j++) {
                minIndex = arr[j].compareTo(arr[minIndex]) > 0 ? minIndex : j;
            }
            SortingHelper.INSTANCE.swap(arr, minIndex, i);
        }
    }

    /**
     * arr[i,n)已排序，arr[0,i) 未排序
     * sort2的基本逻辑是，从后向前扫描，对于每一个i，寻找arr[0...i]区间中的最大值，记这个最大值的索引是maxIndex，
     * 然后，只需要每次将arr[i]和arr[maxIndex]交换位置即可。
     * <p>
     * 在sort2中，从后向前，每次找前面未排序部分的最大值，和arr[i]交换
     *
     * @param arr
     * @param <E>
     */

    public <E extends Comparable<E>> void sort2(E[] arr) {
        for (int i = arr.length - 1; i >= 0; i--) {
            int maxIndex = i;
            //从前到后遍历未排序部分
            //for (int j = 0; j <= i; j++) {
            //   maxIndex = arr[j].compareTo(arr[maxIndex]) > 0 ? j : maxIndex;
            //}
            //从后到前便利未排序部分
            for (int j = i; j >= 0; j--) {
                maxIndex = arr[j].compareTo(arr[maxIndex]) > 0 ? j : maxIndex;
            }
            SortingHelper.INSTANCE.swap(arr, maxIndex, i);
        }
    }



}
